1. Field of the Invention:
The present invention relates to digital information processing systems, and more particularly relates to microarchitecture hardware implementations in connection with certain mathematical algorithms for improving the computing capacity of such systems.
2. Art Background:
Numerical or mathematical functions are provided within a general purpose digital computer by providing arrangements of hardware components implementing numerical algorithms for the particular functions desired. In general, there exist numerous algorithms for solving the commonly encountered mathematical functions including addition, subtraction, multiplication, division, square root and other root finding functions, exponential and trigonometric functions. Because the available surface area of the silicon substrate on which component devices of the hardware arrangement are fabricated is limited, functional circuitry is shared where possible to reduce the number of unique devices which must be fabricated on the silicon. Accordingly, it is common for certain blocks of circuitry to share two, three, or more mathematical functions. For example, floating point division, integer division and square root generation may all be produced in the same functional block, namely a divider.
Dividers may implement varying forms of division, including integer and floating point forms as referred to above. Moreover, both integer and floating point division may be implemented as restoring or nonrestoring methods. Each is uniquely suited to a particular type of application, with nonrestoring division being favored in quotient determination applications, whereas restoring division is most commonly encountered in determination of remainder. The reason for the foregoing is that nonrestoring division can be made to evaluate multiple bits at a time, wherein a quotient may be determined by two, or even three bits each clock cycle. The basis for multiple bit quotient determination is given in numerous articles and books describing SRT radix n division, including, Fandrianto, Algorithm for High-Speed Shared Radix 4 Division and Radix 4 Square Root (IEEE Publ. No. CH2419-0/87/0000/0073, 1987), and Hennessy and Patterson, Computer Architecture--A Quantitative Approach (1990).
In nonrestoring division, the divisor is iteratively subtracted from the dividend and the remainder evaluated. However, if the remainder is negative, the divisor subtracted from the dividend in the iteration producing the negative remainder will not be restored to the quotient. Rather, with the use of redundant quotient digits, the remainder will be corrected in later iterations, wherein the sign of the remainder is checked. If negative, the divisor is added back to the remainder and the quotient is decremented by 1, thus restoring the operation. In contrast, in dividers implementing restoring division, the sign of the remainder is checked after each subtraction of the dovisor. If the remainder is negative, the operation is immediately restored by adding the divisor back to the remainder and decrementing the quotient by 1, accordingly.
Many implementations of division algorithms utilize what is generally termed "redundant notation" or "redundant from" for representing quotients generated in the division hardware. Moreover, many implementations of division algorithms use alternative forms of a quotient, generally referred to as "Q" and "Q-1" forms, which respectively represent the quotient, and the quotient diminished by one. The benefit of redundant notation is that by maintaining Q and Q-1 forms throughout a nonrestoring division operation, the correct quotient may be produced in the final iteration in cases where the remainder has become negative, without restoring the quotient. In other words, if the remainder is negative after the final subtraction of the divisor from the dividend, and if both Q and Q-1 forms are maintained then determination of the final answer is simply a matter of choosing either the quotient Q or Q-1 in accordance with the sign of the remainder. For example, if upon dividing a by b the quotient is determined in the final iteration to be positive, then the final result will simply be the quotient Q. On the other hand, if upon dividing a by b the remainder is negative, then it will be known that the divisor must be added to the previous partial remainder and the quotient diminished by 1, yielding the Q-1 result.
In prior art hardware configurations, division circuits implementing redundant iterative division algorithms have heretofore required separate data paths, storage registers, and logic implementing algorithms to produce both the Q and Q-1 results. Even if Q and Q-1 are generated by a shared data path, an implicit consequence of the prior art generation and retrieval of Q and Q-1 alternative forms is that additional logic and data path width must be provided to accommodate both alternative forms, thereby affecting the speed path of the division circuit.
As will be explained in more detail in the following detailed description, the present invention provides a compact and simple hardware divider arrangement wherein alternative quotient forms Q and Q-1 are generated on the fly in the clock cycle necessary by simply selecting between one of two control signals applied to simple logic gates and an adder. The present invention permits delivery of alternative quotient forms in the clock cycle for steering the final result onto the output data path.